/**
 * 前缀和解法 O(n^2)
 * @param {number[]} arr
 * @return {number}
 */
export var sumOddLengthSubarrays = function (arr) {
  const prefixs = new Array(arr.length + 1).fill(0)
  for (let i = 0; i < arr.length; i++) {
    prefixs[i + 1] = prefixs[i] + arr[i]
  }
  let ans = 0
  let start = 0
  // 外循环查每个数字
  while (start < arr.length) {
    // 内循环查以每个数字为开头的各个奇数长度子数组
    let length = 1
    while (start + length <= arr.length) {
      // 奇数长度子数组的和
      ans += prefixs[start + length] - prefixs[start]
      length += 2
    }
    start++
  }
  return ans
}

/**
 * 官方数学解法，O(n), 见
 * https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/solution/suo-you-qi-shu-chang-du-zi-shu-zu-de-he-yoaqu/
 * @param {number[]} arr
 * @return {number}
 */
export var sumOddLengthSubarrays2 = function (arr) {
  let sum = 0
  const n = arr.length
  for (let i = 0; i < n; i++) {
    const leftCount = i,
      rightCount = n - i - 1
    const leftOdd = Math.floor((leftCount + 1) / 2)
    const rightOdd = Math.floor((rightCount + 1) / 2)
    const leftEven = Math.floor(leftCount / 2) + 1
    const rightEven = Math.floor(rightCount / 2) + 1
    sum += arr[i] * (leftOdd * rightOdd + leftEven * rightEven)
  }
  return sum
}
